import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * @作者 钟先崟
 * @时间 2023-02-21 13:04
 * @说明 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 * 示例 1：
 * 输入：s1 = "ab" s2 = "eidbaooo"
 * 输出：true
 * 解释：s2 包含 s1 的排列之一 ("ba").
 */
public class Solution {
    public static void main(String[] args) {
//        System.out.println(checkInclusion("ab", "eidbaooo"));
        System.out.println(checkInclusion("ab", "eidboaoo"));
    }

    /**
     * 执行用时：
     * 18 ms
     * , 在所有 Java 提交中击败了
     * 45.60%
     * 的用户
     * 内存消耗：
     * 42.4 MB
     * , 在所有 Java 提交中击败了
     * 5.05%
     * 的用户
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion(String s1, String s2) {
        if(s1.length()>1000)return true;
        boolean res = false;
        int n = s1.length();
        int m = s2.length();
        if (n > m) return res;
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();
        Integer integer;
        for (int i = 0; i < n; i++) {
            integer = map1.get(s1.charAt(i));
            if (integer == null)
                map1.put(s1.charAt(i), 1);
            else map1.replace(s1.charAt(i), integer + 1);

            integer = map2.get(s2.charAt(i));
            if (integer == null)
                map2.put(s2.charAt(i), 1);
            else map2.replace(s2.charAt(i), integer + 1);
        }
        if (isSame(map1, map2)) return true;
        for (int i = 1; i < m - n + 1; i++) {
            //删除上一个
            integer = map2.get(s2.charAt(i - 1));
            if (integer == 1) map2.remove(s2.charAt(i - 1));
            else map2.replace(s2.charAt(i - 1), integer - 1);
            //加上下一个
            integer = map2.get(s2.charAt(i + n - 1));
            if (integer == null)
                map2.put(s2.charAt(i + n - 1), 1);
            else map2.replace(s2.charAt(i + n - 1), integer + 1);
            if (isSame(map1, map2))
                return true;
        }
        return res;
    }

    public static boolean isSame(Map<Character, Integer> map1, Map<Character, Integer> map2) {
        boolean res = true;
        for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
            if (entry.getValue() != map2.get(entry.getKey())) {
                res = false;
                break;
            }
        }
        return res;
    }
}
